#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <vector>
#include <memory>

using namespace std;

// 位图在处理大数据时，占用空间比hash表小
// 但是如果数据量小，且个别值非常大，则浪费空间
// 位图能表示的状态比较少

// 找出重复的数据
int main(int argc, const char** argv) {
    vector<int> vec = {10,22,33,58,98,87,200,87,1200,350,48,14,22,45,66,78};
    // 找出最大值,并根据最大值设置位图大小
    int max = vec[0];
    for (auto val : vec)
    {
        if (val > max) max = val;
    }
    // 申请空间
    int* bitmap = new int[max / 32 + 1];
    unique_ptr<int> p(bitmap);
    // 初始化位图
    memset(bitmap, 0, sizeof(int) * (max / 32 + 1));
    // 遍历数组，将数据对应位置置1
    for (auto val : vec)
    {
        int index = val / 32;
        int offset = val % 32;
        if ((bitmap[index] & (1 << offset)) == 0)
        {
            bitmap[index] |= (1 << offset);
        }
        else
        {
            cout << "duplicate data: " << val << endl;
        }
    }
    // 遍历位图，找出值为1的位置
    for (int i = 0; i < max / 32 + 1; i++)
    {
        for (int j = 0; j < 32; j++)
        {
            if (bitmap[i] & (1 << j))
            {
                cout << "all data: " <<i * 32 + j << endl;
            }
        }
    }
    // delete[] bitmap;
    return 0;
}   